import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:${USER}
 * Date:${YEAR}-${MONTH}-${DAY}
 * ${TIME}
 */
public class Main {


    public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap=new PriorityQueue<>((n1,n2)->n1.val-n2.val);
        for(ListNode node:lists){
            if(node!=null){
                heap.add(node);
            }
        }
        ListNode ret=new ListNode(0);
        ListNode prev=ret;
        while(!heap.isEmpty()){
            ListNode tmp=heap.poll();
            prev.next=tmp;
            prev=prev.next;
            if(tmp.next!=null){
                heap.add(tmp.next);
            }
        }
        return ret.next;
    }

}